package treesNgraphs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * Created by Tzachi on 13/10/2014.
 * <p>
 * You are given a binary tree in which each node contains a value.
 * Design an algorithm to print all paths which sum up to that value.
 * Note that it can be any path in the tree - it does not have to start at the root.
 */
public class AllPathsToSum {

    /**
     * Part 1: Sum has to start from the root - DFS Pre-Order
     */
    public static void allPathsToSum_fromRoot(TreeNode<Integer> node, List<Integer> path, int currentSum, int targetSum) {
        if (node == null) {
            return;
        }
        int value = node.getValue();
        path.add(value);
        currentSum += value;
        if (currentSum == targetSum) {
            System.out.println(path);
        }
        allPathsToSum_fromRoot(node.getLeftChild(), path, currentSum, targetSum);
        allPathsToSum_fromRoot(node.getRightChild(), path, currentSum, targetSum);
    }

    /**
     * Part 2: Sum can start anywhere on the graph - DFS Pre-Order
     */
    public static void allPathsToSum(TreeNode<Integer> node, ArrayList<Integer> path, int level, int targetSum) {
        if (node == null) {
            return;
        }
        int tmp = targetSum;
        path.add(node.getValue());
        for (int i = level; i >= 0; i--) {
            tmp -= path.get(i);
            if (tmp == 0) {
                printPath(path, i, level);
            }
        }
        ArrayList<Integer> pathLeft = new ArrayList<>(path);
        ArrayList<Integer> pathRight = new ArrayList<>(path);

        allPathsToSum(node.getLeftChild(), pathLeft, level + 1, targetSum);
        allPathsToSum(node.getRightChild(), pathRight, level + 1, targetSum);
    }

    private static void printPath(ArrayList<Integer> path, int start, int end) {
        for (int i = start; i <= end; i++) {
            System.out.print(path.get(i) + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        TreeNode<Integer> treeNode = new TreeNode<>(5);
        treeNode.setLeftChild(new TreeNode<>(0));
        treeNode.setRightChild(new TreeNode<>(-5));
        treeNode.getRightChild().setRightChild(new TreeNode<>(5));
//        allPathsToSum_fromRoot(treeNode, new LinkedList<>(), 0, 0);
        allPathsToSum(treeNode, new ArrayList<>(), 0, 0);

    }
}
